#include<bits/stdc++.h>
using namespace std;
int t; 
int gcd(int a,int b){
	return b? gcd(b,a%b):a;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	freopen("never.in","r",stdin);
	freopen("never.out","w",stdout); 
	cin>>t;
	while(t--){
		int a,b;
		cin>>a>>b;
		if(gcd(a,b)!=1){
			if(b%a==0)cout<<b<<"\n";
			else cout<<a+b<<"\n";
		}else{
			long long x=0,ans=a+b;
			for(int i=2;i*i<=a;i++){
				if(a%i==0){
					x=i;
					break;
				}
			} 
			if(x==0)ans+=a;
			else if(x!=2)ans+=2*x;
			x=0;
			for(int i=2;i*i<=b;i++){
				if(b%i==0){
					x=i;
					break;
				}
			} 
			if(x==0)ans+=b;
			else if(x!=2)ans+=2*x;
			cout<<ans<<"\n";
		}
	}
	return 0;
}

